JAVA 散列

简述

JAVA 散列表可以用来以常数平均时间来实现 insert 和查找操作，但它不能保证存储对象的大小顺序。例如它不能查找最小值、最大值或者找出在某一范围内的项，除非准确使用一个字符串
在使用时，需注意：

其应用场景也很多，包括但不限于：

保证表的大小为素数
key 为字符串
将字符串的 ascii 值（或unicode）加起来
- 缺点：当 tableSize 很大时，不能保证均匀分配，一般会集中在表的前端
计算 key 的前三个字符得到的值然后处理
- 公式：$x + 27 y + 729 z$
  ps:x,y,z分别表示前三个字符所处字母表的位置，例如字母A，x=1；27表示26个字母加上一个空格
- 缺点：虽然理论上有$26^3$个组合，但实际上有效组合(构成有意义的单词)只有2851个组合，所以当 tableSize 很大时依旧无法保证均匀分配。
根据Horner 法则计算一个 37 的多项式(涉及关键字中的所有字符，并且一般可以分布得很好，但当字符串很长时，不使用所有字符)
- 公式： $\sum_{i=0}^{KeySize-1}Key[KeySize-i-1]*37^i$

影响查找效率的重要因素装填因子 $\lambda$

装填因子 $\lambda$ 为散列表中的元素个数对该表大小的比。
而一次成功的查找则需要遍历大约 $1+\lambda/2$ 个链
一般法则

使得表的大小与预料的元素个数大致相等，即装填因子$\lambda\approx1$
如果装填因子大于1，则应扩大散列表的大小
缺点

给新单元分配地址需要时间，因此会导致算法的减慢，同时算法还要求对第二种数据结构的实现

即不用链表的方法（探测散列表）

总体思路
当发生冲突时，尝试另外一些单元，直到找到空的单元为止。可以利用以下公式来寻找
$h_i(x)=(hash(x)+f(i))\ \ mod\ \ TableSize$ 且 $f(0)=0$
其中$f(i)$是冲突解决方法，$h_i(x)$为元素位置
特点
- 该解决方法所需要的表比分离链接法所需要的表要大，一般来说，对于探测散列表，其装填因子$\lambda$应该低于0.5
- 在探测散列表中，标准的删除操作不能执行，因为相应的单元可能已经引起过冲突，元素绕过他存在了别处。因此探测散列表需要懒惰删除。

$f(i)=i$
成功查找的预期探测次数为 $\frac{1}{2}(1+1/(1-\lambda))$
不成功查找的预期探测次数为 $\frac{1}{2}(1+1/(1-\lambda)^2)$
插入的预期探测次数为 $\frac{1}{2}(1+1/(1-\lambda)^2)$
查找次数随 $\lambda$变化的曲线图
总结
线性探测法容易造成聚集，当$\lambda>0.5$时查找次数开始明显随着$\lambda$的增大而快速增多，但当$\lambda<=0.5$时则查找次数较小，例如当$\lambda=0.5$时，不成功查找约2.5次，成功查找约1.5次

$f(i)=i*hash_2(x)$
$hash_2(x)$选的不好将会是灾难性的，该函数一定不能算得0值且保证所有单元都能被探测到也是很重要的。
一般认为$hash_2(x)=R-(x\ mod\ R)$（其中R是小于 TableSize 的素数）将起到良好的作用
应保证两个散列表的大小均为素数，否则就有可能导致无法插入新的元素
当双散列正确实现时，模拟表明，预期的探测次数几乎和随机冲突解决的方法情形相同，这使得双散列算法理论上很具有吸引力。但对于像串这样的关键字，它们的散列函数计算起来相当麻烦，这时可以考虑使用平方探测法

一般当装载因子$\lambda$>=某个值（例如0.5）时，就可以考虑再散列，扩大表，以防止插入失败或者查找次数增多。
再散列的方法有很多例如，建立另外一个大约两倍大的表，扫描整个原始散列表，计算每个（未删除的）元素的新散列值并将其插入到新表中。
何时使用再散列，一般有三个策略：

HashMap类和 HashSet 类，他们通常是使用分离链接散列来实现的，要求存储的对象必须有：

当数据量过大以至于装不进主存的时候，就需要用到可拓散列了